package problem394;

import java.util.Stack;

//394. 字符串编码
//https://leetcode.cn/problems/decode-string/

class Solution {
    public String decodeString(String _s) {
        char[] s = _s.toCharArray();
        int n = s.length;
        Stack<Integer> nums = new Stack<>();
        Stack<Character> strs = new Stack<>();
        int i = 0;
        while(i < n) {
            if(s[i] >= 0 && s[i] <= '9') {
                int tmp = 0;
                while(i < n && s[i] >= 0 && s[i] <= '9') {
                    tmp *= 10;
                    tmp += s[i++] - '0';
                }
                nums.push(tmp);
            }else if(s[i] == '[' || ( s[i] >= 'a' && s[i] <= 'z')){
                strs.push(s[i++]);
            }else if(s[i] == ']') {
                StringBuffer str = new StringBuffer();
                while(strs.peek() != '[') {
                    str.append(strs.pop());
                }
                strs.pop();

                str = str.reverse();
                int cnt = nums.pop();
                for(int j = 0; j<cnt; j++) {
                    for(int k = 0; k<str.length(); k++) {
                        strs.push(str.charAt(k));
                    }
                }
                i++;
            }
        }

        StringBuffer ret = new StringBuffer();
        while(!strs.isEmpty()) {
            ret.append(strs.pop());
        }
        return ret.reverse().toString();
    }
}